Euler Problem 47

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 × 7
15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct prime factors. What is the first of these numbers?



In [1]:

    
N = 200000
sieve = [0] * N
prime_factors = [0] * N
run = 0
for n in range(2, N):
    if sieve[n] == 0:
        sieve[n] = n
        for m in range(n*n, N, n):
            sieve[m] = n
    q = n // sieve[n]
    if q % sieve[n] == 0:
        prime_factors[n] = prime_factors[q]
    else:
        prime_factors[n] = prime_factors[q] + 1
    if prime_factors[n] == 4:
        run += 1
        if run == 4:
            print(n-3)
            break
    else:
        run = 0



In [ ]: